package com.singzi.leetcode.N400;

import java.util.ArrayList;
import java.util.List;

public class T0386 {
    public static void main(String[] args) {
        Solution0386 solution0386 = new Solution0386();
        System.out.println(solution0386.lexicalOrder(80));
    }
}
class Solution0386 {
    List<Integer> ans = new ArrayList<>();
    public List<Integer> lexicalOrder(int n) {

        List<Integer> list = new ArrayList<>();
        list.add(1);
        backTrack(list, n);
        return  ans;

    }
    public void backTrack(List<Integer> list, int n){
        if(sumList(list) > n) return;
        if(sumList(list) <= n){
            ans.add(sumList(list));
            list.add(0);
            backTrack(list, n);
            list.remove(list.size()-1);
            if(list.get(list.size()-1) < 9){
                list.add(list.get(list.size()-1)+1);
                list.remove(list.size()-2);
                backTrack(list, n);
            }

        }
    }
    public int sumList(List<Integer> list){
        int sum = 0;
        for(int num:list){
            sum = sum*10 + num;
        }
        return sum;
    }
}